NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/864

Text File | 1996-08-05 | 4.5 KB | 100 lines

Newsgroups: comp.lang.c
Path: news.sprintlink.net!eskimo!scs
From: [e-mail] (Steve Summit)
Subject: Re: start array at k, not 0
X-Nntp-Posting-Host: eskimo.com
Message-ID: <[e-mail]>
Keywords: Numerical Recipes in C
Sender: [e-mail] (News User Id)
Organization: schmorganization
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Tue, 9 Jan 1996 18:42:35 GMT

In article <[e-mail]>, [e-mail] writes:
> In article <[e-mail]>, [e-mail] (Tim Butler) writes:
>>[e-mail] (Mike Rubenstein) writes:
>>: It's unfortunate that the authors of this book didn't bother to learn
>>: C before writing it.  As anyone who has read the FAQ [6.13] knows,
>>: this results in undefined behavior.
>>
>> They have addressed that in the second edition. To retain the ability
>> to start indexing at one, they "waste" that first element. They
>> allocate one element extra.
>
> Sorry, wrong.

Not quite.

> From the second edition, 1992 (ISBN 0-521-43108-5),
> page 19 (emphasis on PERVERSELY mine):
>
> "But suppose that your vector of length 7, now call it a ... is
> PERVERSELY a native C, zero-offset array. ... Heaven help you! ... You
> simply invoke someroutine(a-1,7) ... We want to free you from the
> zero-offset thinking that C encourages ...
>
> Of course, nrutil.c in Appendix B uses the same WRONG trick.  Please,
> realize that Press, Teukolsky, Vetterling and Flannery MAY know
> algorithms... but FOR SURE they do NOT know C.

Well, it's obvious that plenty of people by now have made them
aware of the problem.  Tim Butler is right: the Numerical Recipes
(second edition) code is correct for 1-based arrays, and Appendix
B in that edition devotes several paragraphs to the topic:

    Strictly speaking, this scheme is not blessed by the ANSI
    C standard.  The problem is *not* the fact that b-1
    points to unallocated storage: location b-1 will never be
    referenced without an increment back into the allocated
    region.  Rather, the problem is that it might happen in
    rare cases (and probably only on a segmented machine)
    that the expression b-1 has *no representation at all*.
    If this occurs, then there is no guarantee that the
    relation b=(b-1)+1 is satisfied.

    In practice, this is much less of a problem than one
    might think.  We are not aware of any compiler or machine
    on which b=(b-n)+n fails to be true for small integer n...
    The memory allocation routines in the First Edition of
    Numerical Recipes in C, in wide use since 1988, all have
    this "problem," and we have had not even a single report
    of their failure in this respect (notwithstanding the
    many readers who have told us that *theoretically* it
    could fail)...

    Despite the absence of any experimental (as opposed to
    theoretical) problem, we have taken some steps in this
    edition to make our vector and matrix allocation routines
    more ANSI compliant.  In the listing that follows, the
    parameter NR_END is used as a number of extra storage
    locations allocated *at the beginning* of every vector or
    matrix block, simply for the purpose of making offset
    pointer representations guaranteed-representable.  We set
    NR_END to a default value of 1.  This has the effect of
    making all *unit-offset* allocations... be strictly ANSI
    compliant.  With NR_END = 1, the number of storage
    locations wasted is fairly negligible.  Allocations with
    offsets other than 1... are still theoretically
    non-compliant, but are virtually unknown in our routines.

[Preceding text all from Numerical Recipes in C, Second Edition,
1992, ISBN 0-521-43108-5, Appendix B, p. 941; all emphasis theirs.]

So, despite their somewhat grudging tone and their dangerous
suggestion that computing is properly an experimental science,
I think they've made a pretty good compromise.  People who
ridicule Numerical Recipes usually claim that they ought to
"just" convert all the algorithms to be 0-based, but I tend to
agree with the authors that the algorithms would then "acquire a
baggage of additional arithmetic in array indices that is, at
best, distracting" [p. 18].  Wasting an array element to make
1-based subscripting convenient is hardly an unknown or
unthinkable practice: no less an authority than K&R explicitly
recommends it (section 5.7), at least when space is not at a
premium.  (To be sure, wasting an entire row and column, to
achieve a 1-based 2-dimensional array, can be considerably more
expensive.)

                    Steve Summit
                    [e-mail]